package mysgoog.brown.dragon;

import java.util.*;
import mysgoog.brown.*;

/*
 fixed by wxa
 */

public class Search
{

    private static final int depth = 3;
    public static int size = 13 * 13;

    /*
     * if moves[] is null , means we only want to know if it can be captured.
     * only require that origin keep updating its stones info
     */
    private static int[] board = new int[Brown.maxSize];

    // ========

    private static int[][] libs = new int[Brown.maxSize][Brown.maxSize];
    private static int[] libn = new int[Brown.maxSize]; // if libn[k]> depth,
                                                        // just record depth
                                                        // don't record it in
                                                        // libs(it's useless)
    private static int[] next_stone = new int[Brown.maxSize];
    // private static boolean[] accessed = new boolean[Brown.maxSize];

    // used in completeSet() record all the added liberties
    private static boolean[] complete = new boolean[Brown.maxSize];
    // used in DFS() to build libn ,libs
    private static boolean[] dfs = new boolean[Brown.maxSize]; // connected
                                                               // stone
    private static boolean[] dfs_lib = new boolean[Brown.maxSize]; // liberties
    private static int[] queue = new int[Brown.maxSize];
    private static int[] queue2 = new int[Brown.maxSize];

    private static boolean[][] capture_innerAccess = new boolean[(depth + 1) * (depth + 1)][Brown.maxSize];
    private static boolean[][] defend_innerAccess = new boolean[(depth + 1) * (depth + 1)][Brown.maxSize];

    private static boolean[] getArrayCapture(int n, int steps)
    {
        Lib.assertTrue(n <= depth);
        return capture_innerAccess[n * (depth + 1) + steps];
    }

    private static boolean[] getArrayDefend(int n, int steps)
    {
        Lib.assertTrue(n <= depth);
        return defend_innerAccess[n * (depth + 1) + steps];
    }

    private static final int NONEED_DEFEND = -1; // too many liberties

    static public int Capture(int pos, int[] moves)
    {
        initial();
        return Capture(pos, moves, null, depth);
    }

    /*
     * return -1 if there's no need to defend
     */
    static public int Defend(int pos, int[] moves)
    {
        initial();
        if (libn[pos] > depth)
            return NONEED_DEFEND;

        return Defend(pos, moves, null, depth);
    }

    static private int Capture1(int pos, int[] moves, boolean[] accessed, int steps)
    {
        int n = libn[pos];
        Lib.assertTrue(n == 1 && steps > 0);

        if (accessed != null)
            accessed[libs[pos][0]] = true;
        if (moves != null)
            moves[0] = libs[pos][0];
        return 1;
    }

    static private int Defend1(int pos, int[] moves, boolean[] accessed, int steps)
    {
        Lib.log("beg8");

        int n = libn[pos];
        int lib = libs[pos][0]; // will be use inside the function
        Lib.assertTrue(n == 1 && steps > 0);

        if (accessed != null)
            accessed[lib] = true;

        int resn = 0;
        int opp_color = Brown.OTHER_COLOR(board[pos]);

        addMove(lib, board[pos]);
        if (libn[pos] > 1)
        {
            if (moves != null)
                moves[resn] = lib;
            ++resn;
        }
        undoMove(lib);

        int next = pos;
        do
        {
            int i = Brown.I(next);
            int j = Brown.J(next);

            for (int k = 0; k < 4; ++k)
            {
                int ai = i + Brown.deltai[k];
                int aj = j + Brown.deltaj[k];
                int apos = Brown.POS(ai, aj);
                if (Brown.on_board(ai, aj) && board[apos] == opp_color && libn[apos] == 1)
                {
                    if (accessed != null)
                        accessed[libs[apos][0]] = true;

                    if (moves != null)
                    {
                        int k2 = 0;
                        for (; k2 < resn; ++k2)
                        {
                            if (libs[apos][0] == moves[k2])
                                break;
                        }
                        if (k2 == resn)
                        {
                            moves[resn++] = libs[apos][0];
                        }
                    } else
                        resn = 1;
                }
            }

            next = next_stone[next];
        } while (next != pos);

        Lib.log("end8");
        return resn;
    }

    static private int Capture(int pos, int[] moves, boolean[] accessed, int steps)
    {

        int n = libn[pos];
        Lib.log("Capture beg size" + n + "," + steps);
        if (n > steps)
            return 0;
        if (n == 1)
            return Capture1(pos, moves, accessed, steps);

        int resn = 0;

        if (n == 2)
            resn = captureLadder(pos, moves);

        int my_color = Brown.OTHER_COLOR(board[pos]);
        int[] tmplibs = new int[n];
        System.arraycopy(libs[pos], 0, tmplibs, 0, n);

        Lib.log("Capture beg 2 (" + n + ")");

        if (steps == n)
        {
            Lib.log("Capture beg 3+" + n);
            for (int k = 0; k < n; ++k)
            {
                addMove(tmplibs[k], my_color);
                if (accessed != null)
                {
                    Lib.log("Capture beg 3 +" + tmplibs[k]);
                    accessed[tmplibs[k]] = true;
                }
                // not suicide
                if (libn[tmplibs[k]] > 0)
                {
                    if (Defend(pos, null, accessed, steps - 1) == 0)
                    {
                        Lib.log("Capture beg 5");
                        if (moves != null)
                        {
                            int k2 = 0;
                            for (; k2 < resn; ++k2)
                            {
                                if (moves[k2] == tmplibs[k])
                                    break;
                            }
                            if (k2 == resn)
                                moves[resn++] = tmplibs[k];
                        } else
                            resn = 1;
                    }
                }
                undoMove(tmplibs[k]);
            }
        } else
        {
            boolean[] innerAccessed = getArrayCapture(n, steps);
            Arrays.fill(innerAccessed, 0, size, false);
            Lib.log("Capture beg 4");
            // step 1
            Defend(pos, null, innerAccessed, steps - 1); // n!=1
            for (int k = 0; k < n; ++k)
                innerAccessed[libs[pos][k]] = true;
            // step 2
            completeSet(innerAccessed, steps);
            // step 3
            for (int k = 0; k < size; ++k)
            {
                if (innerAccessed[k])
                {
                    if (accessed != null)
                        accessed[k] = true;
                    Lib.log("beg6");
                    addMove(k, my_color);
                    // not suicide
                    if (libn[k] > 0)
                    {
                        if (Defend(pos, null, accessed, steps - 1) == 0)
                        {
                            if (moves != null)
                            {
                                int k2 = 0;
                                for (; k2 < resn; ++k2)
                                {
                                    if (moves[k2] == k)
                                        break;
                                }
                                if (k2 == resn)
                                    moves[resn++] = k;
                            } else
                                resn = 1;
                        }
                    }
                    undoMove(k);
                    Lib.log("end6");
                }
            }
        }
        return resn;
    }

    static private int Defend(int pos, int[] moves, boolean[] accessed, int steps)
    {

        int n = libn[pos];
        Lib.log("beg defend size(" + n + ")");
        Lib.assertTrue(n > 0);

        if (n > steps)
        {
            for (int k = 0; k < n; ++k)
                accessed[libs[pos][k]] = true;
            return NONEED_DEFEND;
        }
        int my_color = board[pos];
        int resn = 0;

        if (n == 1)
            return Defend1(pos, moves, accessed, steps);

        boolean[] innerAccessed = getArrayDefend(n, steps);
        Arrays.fill(innerAccessed, false);
        for (int k = 0; k < n; ++k)
            innerAccessed[libs[pos][k]] = true;

        // step 1
        Capture(pos, moves, innerAccessed, steps - 1);

        // step2
        completeSet(innerAccessed, steps);
        // step 3

        Lib.log("beg defend 2");
        int counter = 0;
        for (int k = 0; k < innerAccessed.length; ++k)
        {
            if (innerAccessed[k])
            {
                ++counter;
                if (accessed != null)
                    accessed[k] = true;
                addMove(k, my_color);
                // not suicide
                if (libn[k] > 0)
                {
                    Lib.log("beg defend 3");
                    if (Capture(pos, null, accessed, steps) == 0)
                    {
                        Lib.log("beg defend 4");
                        if (moves != null)
                        {
                            int k2 = 0;
                            for (; k2 < resn; ++k2)
                            {
                                if (moves[k2] == k)
                                    break;
                            }
                            if (k2 == resn)
                                moves[resn++] = k;
                        } else
                            resn = 1;
                    }
                }
                undoMove(k);
            }
        }
        Lib.log("end7 +" + counter);
        return resn;
    }

    /*
     * capture worm(with 2 liberties) (steps>=2) don't add all the stones in
     * access , since they are too much check if the worm can be captured by
     * ladder
     */
    static private int captureLadder(int pos, int[] moves)
    {
        Lib.log("Ladder beg");
        int n = libn[pos];
        Lib.assertTrue(n == 2);
        int lib1 = libs[pos][0];
        int lib2 = libs[pos][1];

        int direction = diagonal(lib1, lib2);
        if (direction < 0)
            return 0;
        int res = 0;
        if (ladder(direction, pos))
        {
            if (moves != null)
                moves[res++] = lib1;
            else
                return 1;
        }
        if (ladder(diagonal(lib2, lib1), pos))
        {
            if (moves != null)
                moves[res++] = lib2;
            else
                return 1;
        }
        Lib.log("Ladder end" + res);
        return res;
    }

    static private int[] ladderArr = new int[Brown.maxSize];
    static private boolean ladder(int direction, int pos)
    {
        int n = libn[pos];
        if (n != 2)
            return false;
        int opp_color = board[pos];
        int mycolor = Brown.OTHER_COLOR(opp_color);

        int lib1 = libs[pos][0];
        int lib2 = libs[pos][1];
        // maybe opposite
        if (diagonal(lib1, lib2) != direction)
        {
            lib1 = libs[pos][1];
            lib2 = libs[pos][0];
        }
        // not parallel
        if (diagonal(lib1, lib2) != direction)
            return false;

        addMove(lib1, mycolor);
        int def1 = Defend1(pos, ladderArr, null, 1);
        if (def1 == 0)
        {
            undoMove(lib1);
            return true;
        } else if (def1 == NONEED_DEFEND || def1 > 1)
        {
            undoMove(lib1);
            return false;
        } else if (ladderArr[0] == lib2)
        {
            // only one lib
            addMove(lib2, opp_color);
            boolean b = ladder(direction, pos);
            undoMove(lib2);
            undoMove(lib1);
            return b;
        } else
        {
            undoMove(lib1);
            return false;
        }
    }

    static private int[] digI = { 1, -1, 1, -1 };
    static private int[] digJ = { 1, 1, -1, -1 };
    static private int diagonal(int pos1, int pos2)
    {
        for (int k = 0; k < 4; ++k)
        {
            if (Brown.POS(Brown.I(pos1) + digI[k], Brown.J(pos1) + digJ[k]) == pos2)
                return k;
        }
        return -1;
    }

    /*
     * add all potential points for accessed
     */
    static private void completeSet(boolean[] accessed, int maxlibn)
    {
        Arrays.fill(complete, 0, size, false);

        for (int k = 0; k < accessed.length; ++k)
        {
            if (accessed[k])
            {
                for (int k1 = 0; k1 < 4; ++k1)
                {
                    int ai = Brown.I(k) + Brown.deltai[k1];
                    int aj = Brown.J(k) + Brown.deltaj[k1];
                    int apos = Brown.POS(ai, aj);

                    if (Brown.on_board(ai, aj) && board[apos] != Brown.EMPTY
                            && libn[apos] <= maxlibn)
                    {
                        for (int k2 = 0; k2 < libn[apos]; ++k2)
                        {
                            complete[libs[apos][k2]] = true;
                        }
                    } else if (Brown.on_board(ai, aj) && board[apos] == Brown.EMPTY)
                    {
                        complete[apos] = true;
                    }
                }
            }
        }
        for (int k = 0; k < size; ++k)
            if (complete[k])
                accessed[k] = true;

    }

    /*
     * update libs[],libn[],board[], next_stone[]
     */
    static private void addMove(int pos, int color)
    {
        board[pos] = color;
        for (int k = 0; k < 4; ++k)
        {
            int ai = Brown.I(pos) + Brown.deltai[k];
            int aj = Brown.J(pos) + Brown.deltaj[k];
            int apos = Brown.POS(ai, aj);
            if (Brown.on_board(ai, aj) && board[apos] == Brown.OTHER_COLOR(color))
            {
                DFS1(apos); // only find libs
            }
        }
        DFS(pos); // find libs and worms
    }
    static private void undoMove(int pos)
    {
        int color = board[pos];
        int opp_color = Brown.OTHER_COLOR(color);

        board[pos] = Brown.EMPTY;
        for (int k = 0; k < 4; ++k)
        {
            int ai = Brown.I(pos) + Brown.deltai[k];
            int aj = Brown.J(pos) + Brown.deltaj[k];
            int apos = Brown.POS(ai, aj);
            if (Brown.on_board(ai, aj))
            {
                if (board[apos] == color)
                    DFS(apos);
                if (board[apos] == opp_color)
                    DFS1(apos);
            }
        }
    }
    /*
     * build libn,libs, next_stone
     */
    static private void DFS(int pos)
    {
        Arrays.fill(dfs, 0, size, false);
        Arrays.fill(dfs_lib, 0, size, false);
        int beg = 0, end = 1;
        queue[0] = pos;
        dfs[pos] = true;
        while (beg != end)
        {
            for (int k = 0; k < 4; ++k)
            {
                int ai = Brown.I(queue[beg]) + Brown.deltai[k];
                int aj = Brown.J(queue[beg]) + Brown.deltaj[k];
                int apos = Brown.POS(ai, aj);
                if (Brown.on_board(ai, aj))
                {
                    if (board[pos] == board[apos] && !dfs[apos])
                    {
                        dfs[apos] = true;
                        queue[end++] = apos;
                        if (end == queue.length)
                            end = 0;
                    } else if (board[apos] == Brown.EMPTY)
                    {
                        dfs_lib[apos] = true;
                    }
                }
            }
            ++beg;
            if (beg == queue.length)
                beg = 0;
        }

        int stones = 0;
        int lib_num = 0;
        for (int k = 0; k < size; ++k)
        {
            if (dfs[k])
                queue[stones++] = k; // the stones
            if (dfs_lib[k])
                queue2[lib_num++] = k;
        }

        for (int k = 0; k < stones; ++k)
        {
            if (k != stones - 1)
                next_stone[queue[k]] = queue[k + 1];
            else
                next_stone[queue[k]] = queue[0];
            libn[queue[k]] = lib_num;
            System.arraycopy(queue2, 0, libs[queue[k]], 0, lib_num);
        }
    }
    /*
     * build only libn,libs
     */
    static private void DFS1(int pos)
    {

        Arrays.fill(dfs_lib, 0, size, false);

        int next = pos;
        do
        {
            for (int k = 0; k < 4; ++k)
            {
                int ai = Brown.I(next) + Brown.deltai[k];
                int aj = Brown.J(next) + Brown.deltaj[k];
                int apos = Brown.POS(ai, aj);
                if (Brown.on_board(ai, aj) && board[apos] == Brown.EMPTY)
                {
                    dfs_lib[apos] = true;
                }
            }
            next = next_stone[next];
        } while (next != pos);

        int lib_num = 0;
        for (int k = 0; k < size; ++k)
        {
            if (dfs_lib[k])
                queue2[lib_num++] = k;
        }

        next = pos;
        do
        {
            libn[next] = lib_num;
            System.arraycopy(queue2, 0, libs[next], 0, lib_num);
            next = next_stone[next];
        } while (next != pos);

    }

    static private void initial()
    {
        System.arraycopy(Brown.board, 0, board, 0, size);
        System.arraycopy(Brown.next_stone, 0, next_stone, 0, size);

        for (int i = 0; i < size; ++i)
        {
            if (board[i] != Brown.EMPTY && DragonMgr.worms[i].origin == i)
            {
                DFS1(i); // only libs
            }
        }
    }
}
